package com.yin.algorithms;

import com.yin.Sort;
import com.yin.Util;

public class BubbleSort implements Sort {

    @Override
    public void sort(int[] arr) {

        //每次找一个最大的数放在后面
        //i -> 要比较多少次，每次找出最大值后剩下的数 组成的数组的长度 -> 余下数组.length
        //只剩下一个数时剩余数组必定是有序的所以只用排(arr.length - 1)次
        for(int i = arr.length - 1; i > 0; i--) {

            //每次把最大的数挪到后面
            //j < i -> j < 余下数组.length
            //实质上是在遍历余下数组
            for(int j = 0; j < i; j++) {

                //如果当前数比下一个数要打则往后挪(交换位置)
                //如果当前数比下一个数小则j指向下一个数
                if(arr[j] > arr[j + 1]) {

                    Util.swap(arr, j, j + 1);
                }
            }
        }
    }
}
